//************************************************************
//    > File Name: heap_sort.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月14日 17:49:07
//***********************************************************
//lintcode #464
#include<bits/stdc++.h>
using namespace std;
void heap_adjust(vector<int>& a,int p,int n){
	for(int maxid=p;p<(n>>1);p=maxid){
		if((p<<1)+1<n && a[(p<<1)+1]>a[maxid])
			maxid=(p<<1)+1;
		if((p<<1)+2<n && a[(p<<1)+2]>a[maxid])
			maxid=(p<<1)+2;
		if(maxid==p) break;
		swap(a[maxid],a[p]);
	}
}
void heap_sort(vector<int>& a,int n){
	for(int i=(n>>1)-1;i>-1;heap_adjust(a,i--,n));
	for(int i=n-1;i>0;--i){
		swap(a[0],a[i]);
		heap_adjust(a,0,i);
	}
}
int main()
{
	vector<int> a;
	a.push_back(6);
	a.push_back(4);
	a.push_back(8);
	a.push_back(2);
	a.push_back(9);
	a.push_back(3);
	a.push_back(7);
	heap_sort(a,a.size());
	for(int i=0;i<a.size();i++)
		cout<< a[i] <<" ";
	cout<<endl;
	return 0;
}
